πŸ‘©β€πŸ’» 81302. 거리두기 ν™•μΈν•˜κΈ°

@Seongukbaek Posted May 03, 2022 Β· Updated May 03, 2022 Β· 4 min read

문제

Programmers - 거리두기 ν™•μΈν•˜κΈ°

πŸ“ Logic

private int bfs(int x, int y) { Queue<Loc> queue = new LinkedList<>(); boolean[][] visited = new boolean[5][5]; int keep = 1; visited[x][y] = true; queue.add(new Loc(x, y, 0)); while(!queue.isEmpty()) { Loc now = queue.poll(); for (int i = 0; i < 4; i++) { int nx = now.x + rangeX[i]; int ny = now.y + rangeY[i]; if (!isIn(nx, ny)) continue; if (visited[nx][ny]) continue; int nDist = now.dist + 1; if (nDist > 2) continue; char nP = place[nx].charAt(ny); if (nP == 'P') return 0; if (nP == 'X') continue; visited[nx][ny] = true; queue.add(new Loc(nx, ny, nDist)); } } return keep; }
  • μ‘μ‹œμžμ˜ μœ„μΉ˜λΆ€ν„° BFSλ₯Ό μ‹œμž‘ν•œλ‹€.

    • λ‹€μŒ λ°©λ¬Έν•  지점이 이미 λ°©λ¬Έν–ˆκ±°λ‚˜, λ²”μœ„λ₯Ό λ²—μ–΄λ‚œ κ²½μš°λŠ” λ‹€μŒ 지점을 νƒμƒ‰ν•˜κ³ ,
    • 거리가 2보닀 큰 κ²½μš°λŠ” 더 이상 ν™•μΈν•˜μ§€ μ•Šμ•„λ„ 거리두기가 μ§€μΌœμ§„ κ²½μš°μ΄λ―€λ‘œ, λ‹€μŒ 지점을 νƒμƒ‰ν•˜κ³ ,
    • 2 μ΄ν•˜μ˜ 거리에 λ‹€λ₯Έ μ‘μ‹œμžκ°€ μžˆλ‹€λ©΄, 거리두기가 μ§€μΌœμ§€μ§€ μ•Šμ€ κ²ƒμœΌλ‘œ, λ°”λ‘œ λ°˜ν™˜ν•œλ‹€.
    • λ˜ν•œ νŒŒν‹°μ…˜μ΄ μ‘΄μž¬ν•œλ‹€λ©΄, 더 이상 ν™•μΈν•˜μ§€ μ•Šμ•„λ„ 거리두기가 μ§€μΌœμ§„ κ²½μš°μ΄λ―€λ‘œ, λ‹€μŒ 지점을 νƒμƒ‰ν•œλ‹€.
    • κ·Έλ ‡μ§€ μ•Šμ€ κ²½μš°μ—λ§Œ ν•΄λ‹Ή μ§€μ μ˜ λ°©λ¬Έ μ—¬λΆ€λ₯Ό updateν•˜κ³  큐에 λ„£λŠ”λ‹€. μ΄λ•Œ, 거리λ₯Ό 1μ”© μ¦κ°€ν•œλ‹€.

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.util.*; class Loc { int x; int y; int dist; public Loc(int x, int y, int dist) { this.x = x; this.y = y; this.dist = dist; } } class WaitingRoom { String[] place; int[] rangeX = { 0, 1, 0, -1 }; int[] rangeY = { 1, 0, -1, 0 }; public WaitingRoom(String[] place) { this.place = place; } public int checkKeepingDistance() { for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { char p = place[i].charAt(j); if (p == 'P') if (bfs(i, j) == 0) return 0; } } return 1; } private int bfs(int x, int y) { Queue<Loc> queue = new LinkedList<>(); boolean[][] visited = new boolean[5][5]; int keep = 1; visited[x][y] = true; queue.add(new Loc(x, y, 0)); while(!queue.isEmpty()) { Loc now = queue.poll(); for (int i = 0; i < 4; i++) { int nx = now.x + rangeX[i]; int ny = now.y + rangeY[i]; if (!isIn(nx, ny)) continue; if (visited[nx][ny]) continue; int nDist = now.dist + 1; if (nDist > 2) continue; char nP = place[nx].charAt(ny); if (nP == 'P') return 0; if (nP == 'X') continue; visited[nx][ny] = true; queue.add(new Loc(nx, ny, nDist)); } } return keep; } private boolean isIn(int x, int y) { return (x < 5 && x >= 0 && y < 5 && y >= 0); } } class Solution { public int[] solution(String[][] places) { int[] answer = new int[5]; int T = 0; while (T < 5) { WaitingRoom wr = new WaitingRoom(places[T]); answer[T++] = wr.checkKeepingDistance(); } return answer; } }

✏️ Review

  • μ²˜μŒμ—λŠ” DFS λ°©μ‹μœΌλ‘œ κ΅¬ν˜„ν–ˆμœΌλ‚˜, λͺ‡λͺ‡ ν…ŒμΌ€μ—μ„œ ν‹€λ Έκ³ , λ‹¨μˆœνžˆ 탐색 λ°©μ‹μ˜ μ°¨μ΄λ‹ˆκΉŒ BFS둜 κ΅¬ν˜„ν•΄λ„ 동일할 것이라 μƒκ°ν–ˆλ‹€.

    • κ·Έλž˜ν”„ 탐색 λ°©μ‹μ˜ λ¬Έμ œκ°€ μ•„λ‹Œ, λ°˜ν™˜ κ°’μ˜ λ°˜ν™˜ 쑰건에 λŒ€ν•œ λ¬Έμ œμ˜€λ‹€.
  • λ‹€μŒ λ°©λ¬Έ 지점에 λŒ€ν•΄ λ§¨ν•΄νŠΌ 거리λ₯Ό ꡬ해보고, 2 μ΄ν•˜μΈμ§€ ν™•μΈν•˜λŠ” λ°©μ‹μ—μ„œ ν˜„μž¬ μ§€μ μ—μ„œ λ‹€μŒ μ§€μ μœΌλ‘œ 이동할 λ•Œλ§ˆλ‹€ dist λ₯Ό 1μ”© μ¦κ°€μ‹œν‚€κ³  κ·Έ 값을 ν•¨κ»˜ μ „λ‹¬ν•΄μ£ΌλŠ” λ°©μ‹μœΌλ‘œ λ³€κ²½ν•˜μ—¬ μ‹œκ°„μ„ 쀄일 수 μžˆμ—ˆλ‹€.
@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€